package leetcode_900;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *FindEventualSafeStates_802 寻找所有的节点，这些节点能到达一个没出出度的节点
 *describe:深搜 AC 99%
 *2018年10月24日 下午1:43:48
 */
public class FindEventualSafeStates_802 {
	 public List<Integer> eventualSafeNodes(int[][] graph) {
	       int N = graph.length;
	       int[] color = new int[N];
	       List<Integer> res = new ArrayList<>();
	       for (int i = 0; i < N; i++) {
	           if (dfs(i, color, graph))
	               res.add(i);
	       }
	       return res;
	   }
	   private boolean dfs(int i, int[] color, int[][] graph) {
	       if (color[i] > 0) {
	           return color[i] == 2;
	       }
	       
	       color[i] = 1;
	       for (int neighbor : graph[i]) {
	           if (color[neighbor] == 2) continue;
	           
	           if (color[neighbor] == 1 || !dfs(neighbor, color, graph)) 
	               return false;
	       }
	       color[i] = 2;
	       return true;
	   }
}
